#include <math.h>
#include <iostream>
#include <vector>
#include <ostream>

using std::cout;
using std::cin;
using std::endl;
using std::vector;

template<typename T>
void swap(T &lhs,T &rhs)
{
    auto temp = lhs;
    lhs = rhs;
    rhs = temp;
}

class Point
{
public:
    Point(int ix = 0, int iy = 0)
    : _ix(ix)
    , _iy(iy)
    {
        // cout << "Point(int = 0, int = 0)" << endl;
    }

    ~Point()
    {
        // cout << "~Point()" << endl;
    }

    void print() const 
    {
        cout << "(" << _ix 
             << ", " << _iy 
             << ")" << endl;
    }

    double getDistance() const
    {
        return hypot(_ix, _iy);
    } 

    int getX() const
    {
        return _ix;
    }

    int getY() const
    {
        return _iy;
    }

    friend std::ostream & operator<<(std::ostream &os, const Point &rhs);

private:
    int _ix;
    int _iy;
};

std::ostream & operator<<(std::ostream &os,const Point &rhs)
{
    os << "(" << rhs._ix
       << ", " << rhs._iy
       << ")";

    return os;
}

//==============================================================================

namespace std
{   
//std命名空间中的less的特化，注意模板的特化
template<>
struct less<Point>
{
    bool operator()(const Point &lhs,const Point &rhs) const
    {
        if(lhs.getDistance() < rhs.getDistance())
        {
            return true;
        }
        else if(lhs.getDistance() == rhs.getDistance())
        {
            if(lhs.getX() < rhs.getX())
            {
                return true;
            }
            else if(lhs.getX() == rhs.getX())
            {
                if(lhs.getY() < rhs.getY())
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }
            else
            {
                return false;
            }
        }
        else
        {
            return false;
        }
    }
};   

}//end of namespace std

bool operator<(const Point &lhs, const Point &rhs)
{
    if(lhs.getDistance() < rhs.getDistance())
    {
        return true;
    }
    else if(lhs.getDistance() == rhs.getDistance())
    {
        if(lhs.getX() < rhs.getX())
        {
            return true;
        }
        else if(lhs.getX() == rhs.getX())
        {
            if(lhs.getY() < rhs.getY())
            {
                return true;
            }
            else
            {
                return false;
            }
        }
        else
        {
            return false;
        }
    }
    else
    {
        return false;
    }
}

struct Comparetion
{
    bool operator()(const Point &lhs,const Point &rhs) const
    {
        if(lhs.getDistance() < rhs.getDistance())
        {
            return true;
        }
        else if(lhs.getDistance() == rhs.getDistance())
        {
            if(lhs.getX() < rhs.getX())
            {
                return true;
            }
            else if(lhs.getX() == rhs.getX())
            {
                if(lhs.getY() < rhs.getY())
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }
            else
            {
                return false;
            }
        }
        else
        {
            return false;
        }
    }
};   

//==============================================================================

namespace std
{   
//std命名空间中的less的特化，注意模板的特化
template<>
struct greater<Point>
{
    bool operator()(const Point &lhs,const Point &rhs) const
    {
        if(lhs.getDistance() > rhs.getDistance())
        {
            return true;
        }
        else if(lhs.getDistance() == rhs.getDistance())
        {
            if(lhs.getX() > rhs.getX())
            {
                return true;
            }
            else if(lhs.getX() == rhs.getX())
            {
                if(lhs.getY() > rhs.getY())
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }
            else
            {
                return false;
            }
        }
        else
        {
            return false;
        }
    }
};   

}//end of namespace std

bool operator>(const Point &lhs, const Point &rhs)
{
    if(lhs.getDistance() > rhs.getDistance())
    {
        return true;
    }
    else if(lhs.getDistance() == rhs.getDistance())
    {
        if(lhs.getX() > rhs.getX())
        {
            return true;
        }
        else if(lhs.getX() == rhs.getX())
        {
            if(lhs.getY() > rhs.getY())
            {
                return true;
            }
            else
            {
                return false;
            }
        }
        else
        {
            return false;
        }
    }
    else
    {
        return false;
    }
}

struct Comparetion_greater
{
    bool operator()(const Point &lhs, const Point &rhs)
    {
        if(lhs.getDistance() > rhs.getDistance())
            return true;
        
        else if(lhs.getDistance() < rhs.getDistance())
            return false;
        
        else{
            if(lhs.getX() > rhs.getX())
                return true;
   
            else if(lhs.getX() == rhs.getX()){
                if(lhs.getY() > rhs.getY())
                    return true;
                else
                    return false;
            }
            else
                return false;
                
        }

    }
};

//==============================================================================

template<typename T,typename Compare = std::less<T>>
class MyQsort
{
public:
    //函数声明不用写出参数名
    MyQsort(T *arr, size_t size, Compare );
    void quick(int left, int right, Compare &);
    int partition(int left, int right, Compare &);
    void print();
private:
    vector<T> _vec;
};

//template<typename T,typename Compare = std::less<T>>
//类模板定义中指定了模板参数的默认值后，如果在类成员函数的定义中再次指定默认模板参数值是不被允许的。
//在类模板的成员函数定义中，不需要再次指定模板参数的默认值，应该直接使用类模板定义时指定的默认值。
template<typename T,typename Compare>
MyQsort<T,Compare>::MyQsort(T *arr, size_t size, Compare com)
{
    for(size_t i = 0; i<size; i++){
        _vec.push_back(arr[i]);
    }

    quick(0, _vec.size()-1, com);
}

template<typename T,typename Compare>
void MyQsort<T,Compare>::quick(int left, int right, Compare &com)
{
    int pivot;
    if(left < right)
    {
        pivot = partition(left, right, com);
        quick(left, pivot -1 ,com);
        quick(pivot + 1, right, com);
    }
}

template<typename T,typename Compare>
int MyQsort<T,Compare>::partition(int left, int right, Compare &com)
{
    T tmp = _vec[left];

    while(left < right){
        //while(_vec[right] < tmp) 这么写没有一般性
        while( left<right && com(tmp, _vec[right]))
            --right;
        if(left<right)
            _vec[left++] = _vec[right];

        while( left<right && com(_vec[left], tmp))
            ++left;
        if(left<right)
            _vec[right--] = _vec[left];
    }
    
    _vec[left] = tmp;
    return left;
}

template<typename T,typename Compare>
void MyQsort<T,Compare>::print(){
    for(auto &elem : _vec)
        cout<<elem<<"  ";
    cout<<endl;
}

int main(int argc,char **argv)
{
    int arr[10] = {1, 2, 4, 5, 8, 6, 3, 7, 2, 9} ;
    MyQsort<int> mqInt(arr, 10, std::less<int>());
    /* MyQsort<int, std::greater<int>> mqInt1(arr, 10, std::greater<int>()); */

    mqInt.print();

    Point par[5] = {Point(1,2), Point(3,4), Point(-1,2), Point(4,5), Point(2,5)};
    //MyQsort<Point> mqPt(par,5,std::less<Point>());
    //MyQsort<Point, std::greater<Point> > mqPt(par,5,std::greater<Point>());
    MyQsort<Point, Comparetion_greater> mqPt(par, 5, Comparetion_greater());
    mqPt.print();

    return 0;

}


